package com.example.learn.hwod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class _01流浪地球 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();

        int[] launches = new int[n];
        Arrays.fill(launches, 2001);
        for (int i = 0; i < e; i++) {
            int t = sc.nextInt();
            int p  =sc.nextInt();
            launches[p] = t;
        }
        for (int i = 0; i <n; i++) {
            for(int j = 0 ;j<n;j++){
                int innerDis = Math.abs(i-j);
                int outDis = n-innerDis;
                int dis = Math.min(outDis,innerDis);
                launches[j] = Math.min(launches[j],launches[i]+dis);
            }
        }
        int maxT = 0;

        ArrayList<Integer> collect = new ArrayList<>();
        for (int p = 0; p < launches.length; p++) {
            int t = launches[p];
            if(t<maxT) continue;
            if(t>maxT) maxT = t;
            collect.add(p);
        }
        StringJoiner joiner = new StringJoiner(" ");
        collect.stream().sorted((a,b)->a-b).forEach(x-> joiner.add(x.toString()));
        System.out.println(maxT);
        System.out.println(joiner);
    }
}